import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: DELL
 * Date: 2023-07-29
 * Time: 10:49
 */
public class ShellSort {

    /**
     * 希尔排序是对直接插入排序的优化
     * 当 gap > 1 的时候, 都是进行一些预排序, 目的是让数组更加趋近于有序.
     * 当 gap == 1 的时候, 数组已经接近于有序了, 这时候进行插入排序就非常的快了.
     * 由于 gap 的取值无法很好的准确确定. 因此希尔排序的时间复杂度非常难以分析
     * TODO : 时间复杂度暂且按照 O(N ^ 1.25) ~ O(1.6 * N ^ 1.25), 并且他是一个不稳定的排序
     */
    public void shellSort(int[] array) {
        int gap = array.length;
        // 最后一组步长划分为 1
        while (gap >= 1) {
            // gap 步长暂时按照 gap / 2 划分
            gap /= 2;
            shell(array, gap);
        }
    }

    /**
     * 希尔排序基于直接插入排序的优化
     *
     * @param array 传入需要排序的数组
     * @param gap   希尔排序划分的步长
     */
    private void shell(int[] array, int gap) {
        // 之所以是 i++ 而并非 i+=2 或者 i+=gap 等等, 是为了一次遍历同时针对 gap 为 2 和 gap 为 3 的分组进行插入排序. 保证一次同时进行
        // 即使前面无论如何拍, i += 多少, 最终 gap 为 1 的时候都会整体的排一次
        // TODO : 但是条件为 i+gap 的话, 有可能出现不是希尔排序, 因为只有最后一组进行了分组, 其他组不一定进行了分组插入排序
        for (int i = gap; i < array.length; i++) {
            int tmp = array[i];
            int j = i - gap;
            for (; j >= 0; j -= gap) {
                // j 和后一个元素 tmp 进行比较
                // array[j] > tmp
                if (array[j] > tmp) {
                    // 调整位置 小的放到前面
                    array[j + gap] = array[j];

                } else {
                    // 前一个比当前小, 不再需要重新排序放回原位置
                    // array[j + 1] = tmp;
                    // 前面有序的前一个最大的数都比当前这个数小, 说明此时无需再排序
                    break;
                }
            }

            // 走到此时, 如果最后一个数最小, 那么 j 一定会回退到 -1 下标处
            array[j + gap] = tmp;
        }
    }

    public static void main(String[] args) {
        int[] array = {9, 1, 2, 5, 7, 4, 8, 6, 3, 5};
        ShellSort shellSort = new ShellSort();
        shellSort.shellSort(array);
        System.out.println(Arrays.toString(array));
    }
}
